/*
 * @lc app=leetcode.cn id=1005 lang=golang
 *
 * [1005] K 次取反后最大化的数组和
 */
package Solutions

import (
	"math"
	"slices"
)

// @lc code=start
func largestSumAfterKNegations(nums []int, k int) int {
	slices.Sort(nums)
	var abs = func(i int) int {
		if i < 0 {
			return -i
		}
		return i
	}
	var sum = 0
	var minAbs = math.MaxInt64
	for _, v := range nums {
		if v < 0 && k > 0 {
			k--
			sum -= v
		} else {
			sum += v
		}
		if minAbs > abs(v) {
			minAbs = abs(v)
		}
	}
	if k&1 != 0 {
		sum -= minAbs * 2
	}
	return sum
}

// @lc code=end
